package com.code.test.second.greedy;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.md
 * <p>
 * 53. 最大子序和
 * 力扣题目链接
 * <p>
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 示例:
 * <p>
 * 输入: [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释:  连续子数组  [4,-1,2,1] 的和最大，为  6。
 */
public class SCode53 {

    /**
     * 求的是最长子序列
     */
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, -7, -5, 4};
        int ret = maxSubArray(nums);
        System.out.println(ret);
    }

    public static int maxSubArray(int[] nums) {
        int ret = Integer.MIN_VALUE;
        int count;
        for (int i = 0; i < nums.length; i++) {
            count = 0;
            for (int j = i; j < nums.length; j++) {
                count += nums[j];
                ret = Math.max(count, ret);
            }
        }
        return ret;
    }

    /**
     * 贪心的逻辑是，如果是累加是负数，则放弃，从新的开始算
     */
    public static int max(int[] nums) {
        int count = 0;
        int sum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            //sum是区间的累加值，上面累加完，看看累加总和多大
            sum = Math.max(sum, count);
            if (count <= 0) {
                count = 0;//重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
        return sum;
    }


}
